package com.wp.leetCode;

/**
 * Created by 王萍 on 2017/8/2 0002.
 */

/**
 * Given a binary tree, find its minimum depth.The minimum depth is the number of
 * nodes along the shortest path from the root node down to the nearest leaf node.
 * 给定一个二叉树，找到其最小深度。最小深度是从根节点到最近叶节点的最短路径的节点数。
 * 注意：是根节点到叶子节点的最短路径。
 */
public class 二叉树的最小深度 {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        //第一组测试
//        node3.left = node2;
//        node3.right = node1;
//        node2.left = node4;
//        node2.right = node5;
//        node4.left = node7;
//        node7.left = node6;

        //第二组测试
//        node1.right = node2;

        //第三组测试
        node1.left = node2;
        node2.left = node3;
        node3.left = node4;
        node4.left = node5;

        System.out.println(run(node1));
    }

    /**
     * 1.root为null，返回0。
     * 2.root的两个节点都为null，返回1。
     * 3.root的一个节点为null，返回1+另一个节点的递归。
     * 4.root的两个节点都不为null，选择最小的。
     * @param root
     * @return
     */
    public static int run(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        else if (root.left == null) return 1 + run(root.right);
        else if (root.right == null) return 1 + run(root.left);
        else {
            int left = run(root.left);
            int right = run(root.right);
            return left < right ? 1 + left : 1 + right;
        }
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
